package roman.algorithm;

public class myLinkedList<T extends Comparable<T>> {
	Node<T> root;
	int size = 0;
	class Node<T>{
		T data;
		Node<T> prev, next;
		public Node(T d){
			data =d;
			prev = null;
			next = null;
		}
	}
	
	public void insert(T data){
		size++;
		if(root==null){
			root = new Node<T>(data);
			return;
		}
		Node<T> tmp = root;
		while(tmp.next!=null)
			tmp = tmp.next;
		tmp.next = new Node<T>(data);
		tmp.next.prev = tmp;
	}
	
	public void delete(Node<T> n){
		if(n==null)
			return;
		if(n.prev!=null)
			n.prev.next = n.next;
		if(n.next!=null)
			n.next.prev = n.prev;
		size--;
		
	}
	
	public Node<T> find(T data){
		Node<T> tmp = root;
		while(tmp!=null){
			if(tmp.data.equals(data))
				return tmp;
			tmp = tmp.next;
		}
		return tmp;
	}
	
	public String toString(){
		StringBuilder sb = new StringBuilder();
		Node<T> tmp = root;
		while(tmp!=null){
			sb.append(tmp.data.toString());
			tmp = tmp.next;
		}
		return sb.toString();
	}
	public void reorder(){
		Node<T> tmp0 = root;
		Node<T> tmp1 = root.next;
		Node<T> tmp2 = root;
		for(int i=0; i<size/2; i++){
			tmp2 = tmp2.next;
		}
		Node<T> tmp3 = tmp2.next;
		
		while(tmp3!=null){
			tmp0.next = tmp2;
			tmp1.prev = tmp2;
			
			tmp3.prev = tmp2.prev;
			tmp2.prev.next = tmp3;
			
			tmp2.prev = tmp0;
			tmp2.next = tmp1;
			
			tmp0 = tmp1;
			tmp2 = tmp3;
			tmp1 = tmp0.next;
			tmp3 = tmp2.next;
		}
		
		tmp0.next = tmp2;
		tmp2.prev = tmp0;
		
	}
	
	public static void main(String[] argv){
		myLinkedList<String> o = new myLinkedList<String>();
		o.insert("A1");
		o.insert("A2");
		o.insert("A3");
		o.insert("A4");
		o.insert("A5");
		o.insert("B1");
		o.insert("B2");
		o.insert("B3");
		o.insert("B4");
		o.insert("B5");
		System.out.println(o);
		o.reorder();
		System.out.println(o);
	}
}